On the structure of sequential search: Beyond ”no free lunch

Abstract. In sequential, deterministic, non-redundant search the algorithm permutes a test function to obtain the search result. The mapping from test functions to search results is a one-to-one correspondence. There is a parti-tion of the set of functions into maximal blocks of functions that are permu-tations of one another. This permits reasoning about search to be reduced to reasoning about search within blocks of functions. It also leads to the defi-nition of the block uniform distribution, in which functions within the same block have the same probability. It is established that the Kullback-Leibler distance to the nearest block uniform distribution is identical for the distri-butions of test functions and search results. The distance is zero if and only if all search algorithms have identically distributed search results. That is, a block uniform distribution of test functions is necessary and sufficient for “no free lunch.”